РЕШУ ОЛИМП, математика: задания, ответы, решения

Поиск
?

в условии в решении в тексте к заданию в атрибутах
Скопировать ссылку на результаты поиска
Класс: 10 11 9
Атрибут

Тип 11 № 3702 Добавить в вариант

Симметричную монету подбросили n раз. Найдите вероятность того, что не встретились два последовательных броска, в которых наблюдался орел?

Решение.

Введем обозначения: О  — орел, Р  — решка. Пусть S_n  — число последовательностей из О и Р длины n, в которых нет двух последовательных символов О (такие последовательности будем называть корректными). Очевидно, что $S_1=2$ и $S_2=3.$ Найдем рекуррентную формулу для вычисления S_n при $n больше 2.$ Рассмотрим всевозможные последовательности длины n оканчивающиеся на P. Очевидно, что такая последовательность будет корректной, тогда и только тогда, когда будет корректной последовательность без последнего символа Р. Но таких последовательностей ровно $S_n минус 1.$ Теперь рассмотрим все последовательности длины n оканчивающиеся на О. Очевидно, что такая последовательность будет корректной, тогда и только тогда, когда будет корректной последовательность без последних двух символов Р и О (предпоследний символ обязательно Р). Следовательно, таких последовательностей ровно $S_n минус 2.$

Получаем рекуррентную формулу для вычисления S_n: $S_1=2,$ $S_2=3$ и $S_n=S_n минус 1 плюс S_n минус 2$ при $n больше 2.$ Очевидно, что это просто смещенная последовательность Фибоначчи $S_n=f_n плюс 2.$ Итоговая вероятность вычисляется по формуле $дробь: числитель: f_n плюс 2, знаменатель: 2 в степени левая круглая скобка n правая круглая скобка конец дроби .$

Ответ: $дробь: числитель: f_n плюс 2, знаменатель: 2 в степени левая круглая скобка n правая круглая скобка конец дроби .$

Ответ:

\frac{f_{n+2}}{2^{n}}.

Решение · Помощь

Тип 0 № 5353 Добавить в вариант

Имеется пирамида, составленная из 10 колец разного диаметра, надетых на палочку так, что меньшее кольцо всегда лежит на большем. Требуется переложить эти кольца на другую палочку (используя вспомогательную третью); при этом запрещено класть большее кольцо на меньшее. Какое наименьшее число перекладываний потребуется?

Решение.

Это известная задача о Ханойской башне, которую часто рассматривают среди первых задач на метод математической индукции. Собственно говоря, для решения этой задачи нам не требуется использовать метод математической индукции, поскольку в ее условии дано конкретное число колец. Разобрав случаи $n=1,2,3$ получим, что потребуются, соответственно, одно, три или семь перекладываний. Для того, чтобы переложить «башню» из четырех колец, необходимо: снять верхние три кольца, затем переложить нижнее кольцо на свободную палочку и, наконец, положить на него три кольца меньшего диаметра. Таким образом, потребуются $7 плюс 1 плюс 7=15$ перекладываний. Решим задачу для произвольного числа n колец. Из приведенного рассуждения сразу следует рекуррентная формула для чисел p_n наименьшего числа перекладываний для башни, состоящей из n колец:

$p_n плюс 1=2p_n плюс 1.$

Действительно, для того, чтобы переложить нижнее, $левая круглая скобка n плюс 1 правая круглая скобка$ -е, кольцо, нам вначале надо переложить n лежащих над ним колец, на что будут затрачено p_n перекладываний. Затем мы переложим нижнее кольцо и потратим еще p_n перекладываний, чтобы поместить на нем n верхних колец. Нетрудно догадаться, что $p_n=2 в степени n минус 1.$ После этого осталось сделать последний шаг, состоящий в применении метода математической индукции для доказательства найденной формулы. Таким образом, осталось решить следующую задачу: известно, что $x_1=1$ и для всех n $x_n плюс 1=2x_n плюс 1.$ Докажите, что $x_n=2 в степени n минус 1.$ База индукции: $x_1=1=2 в степени 1 минус 1.$ Индукционный переход: если $x_n=2 в степени n минус 1,$ то

$x_n плюс 1=2x_n плюс 1=2 умножить на левая круглая скобка 2 в степени n минус 1 правая круглая скобка плюс 1=2 в степени левая круглая скобка n плюс 1 правая круглая скобка минус 2 плюс 1=2 в степени левая круглая скобка n плюс 1 правая круглая скобка минус 1.$

Задача о ханойской башне является одной из лучших задач на индукционный метод рассуждения, в ее решении собственно «метод математической индукции» играет не слишком содержательную роль. Анализ приведенного решения показывает, что существо решения  — в построении так называемого рекурсивного алгоритма.

Ответ: $2 в степени левая круглая скобка 10 правая круглая скобка минус 1=1023.$

Решение · Помощь

Тип 21 № 6530 Добавить в вариант

В задаче номер 4 мы описывали все слова в алфавите {a, b}, разбивающиеся на чередующиеся блоки из букв a и букв b нечётной длины.

Найдите количество таких слов длины 8.

Решение.

Переборное решение.

Поскольку каждый блок имеет нечётную длину, в слово длины 8 состоит из чётного числа блоков (от 2 до 8). Посчитаем количество способов разбить 8 букв на блоки, а затем умножим это количество на 2, так как каждому разбиению соответствуют два слова, одно из которых начинается на a, а второе на b. Если блоков 8, разбиение на блоки однозначно: в каждом по одной букве. Если блоков 6, то у нас 6 способов выбрать среди них тот, который будет иметь длину 3; остальные будут иметь длину 1.

Если блока 4, то у нас два случая: один блок имеет длину 5, остальные длину 1 (это 4 варианта) или два блока имеют длину 3, а оставшиеся два длину 1 (ещё 6 вариантов).

Наконец, если блоков 2, то всё определяется длиной первого блока, которая может принимать нечётные значения от 1 до 7 (4 варианта). Итоговый ответ $2 левая круглая скобка 1 плюс 6 плюс 10 плюс 4 правая круглая скобка =42.$

Рекуррентное решение.

Заметим, что количество слов длины n, начинающихся с а и с b совпадают. Обозначим это количество за $x_n.$ Слово, начинающееся с буквы a может начинаться с ab, если вторая буква b, таких слов $X_n минус 1 .$ Если же вторая буква a, то и третья тоже a. Отделим первые две буквы, и у нас получится слово из $n минус 2$ букв, начинающееся на a. Таких слов $x_n минус 2.$ Получаем рекуррентную формулу $x_n=x_n минус 1 плюс x_n минус 2,$ то есть формулу для чисел Фибоначчи. Значит, ответ это удвоенное число Фибоначчи с соответствующим номером, т. е. $2 * 21=42 .$

Ответ: 42.

Решение · Помощь

Тип 0 № 6724 Добавить в вариант

Найдите и докажите явное выражение (в терминах известных операций на целых числах) для общего члена последовательности, заданной следующей рекуррентным отношением: $a_0=1,$ $a_1=1,$ и $a_n плюс 2= левая круглая скобка n плюс 1 правая круглая скобка левая круглая скобка a_n плюс a_n плюс 1 правая круглая скобка$ для $n больше или равно 0.$

Решение · Помощь

Тип 0 № 7739 Добавить в вариант

В школе математики и программирования лестница с первого этажа на второй этаж состоит из двух пролетов, состоящих из 8 и 9 ступенек. Сколькими способами десятиклассник Вася может спуститься по ней, если он может шагать на следующую ступеньку, или перешагивать через ступеньку, или прыгать через две ступеньки?

Решение.

Найдем рекуррентную формулу, которая выражает число N_k способов для десятиклассника Васи спуститься по лестнице, состоящей из k ступенек, если он может шагать на следующую ступеньку, или перешагивать через ступеньку, или прыгать через две ступеньки.

Если $k=0,$ тогда у Васи имеется только единственный способ остаться на начальном месте  — не шагать, поэтому $N_0=1.$

Если $k=1,$ тогда у Васи имеется только один способ спуститься по лестнице, состоящей из одной ступеньки, то есть шагнуть на следующую ступеньку с начальной нулевой ступеньки, то есть $N_1=N_0=1.$

Если $k=2,$ тогда у Васи имеется два способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с первой ступеньки, на которую можно попасть одним способом, или перешагнуть через ступеньку с начальной нулевой ступеньки, то есть

$N_2=N_0 плюс N_1=1 плюс 1=2.$

Если $k=3,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку со второй ступеньки, на которую можно попасть двумя способами, или перешагнуть через ступеньку с первой ступеньки, на которую можно попасть одним способом, или перешагнуть через две ступеньки с начальной нулевой ступеньки, то есть

$N_3=N_0 плюс N_1 плюс N_2=1 плюс 1 плюс 2=4.$

Если $k=4,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с третьей ступеньки, на которую можно попасть $N_3=4$ способами, или перешагнуть через ступеньку со второй ступеньки, на которую можно попасть $N_2=2$ способами, или перешагнуть через две ступеньки с первой ступеньки, на которую можно попасть $N_1=1$ способом; то есть

$N_4=N_1 плюс N_2 плюс N_3=1 плюс 2 плюс 4=7 .$

Если $k=5,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с четвертой ступеньки, на которую можно попасть $N_4=7$ способами, или перешагнуть через ступеньку с третьей ступеньки, на которую можно попасть $N_3=4$ способами, или перешагнуть через две ступеньки со второй ступеньки, на которую можно попасть $N_2=2$ способом, то есть

$N_5=N_2 плюс N_3 плюс N_4=2 плюс 4 плюс 7=13 .$

Если $k=6,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с пятой ступеньки, на которую можно попасть $N_5=13$ способами, или перешагнуть через ступеньку с четвертой ступеньки, на которую можно попасть $N_4=7$ способами, или перешагнуть через две ступеньки с третьей ступеньки, на которую можно попасть $N_3=4$ способом, то есть

$N_6=N_3 плюс N_4 плюс N_5=4 плюс 7 плюс 13=24 .$

Если $k=7,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с шестой ступеньки, на которую можно попасть $N_6=24$ способами, или перешагнуть через ступеньку с пятой ступеньки, на которую можно попасть $N_5=13$ способами, или перешагнуть через две ступеньки с четвертой ступеньки, на которую можно попасть $N_4=5$ способом, то есть

$N_7=N_4 плюс N_5 плюс N_6=7 плюс 13 плюс 24=44 .$

Если $k=8,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с седьмой ступеньки; на которую можно попасть $N_7=44$ способами, или перешагнуть через ступеньку с шестой ступеньки, на которую можно попасть $N_6=24$ способами, или перешагнуть через две ступеньки с пятой ступеньки, на которую можно попасть $N_5=13$ способом; то есть

$N_8=N_5 плюс N_6 плюс N_7=13 плюс 24 плюс 44=81.$

Наконец, если $k=9,$ тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с восьмой ступеньки, на которую можно попасть $N_8=81$ способами, или перешагнуть через ступеньку с седьмой ступеньки, на которую можно попасть $N_7=44$ способами, или перешагнуть через две ступеньки с шестой ступеньки, на которую можно попасть $N_6=24$ способом, то есть

$N_9=N_6 плюс N_7 плюс N_8=24 плюс 44 плюс 81=149.$

Так как на каждом из двух пролетов лестницы десятиклассник Вася спускается отдельно от другого пролета, поэтому нужно перемножить полученные два числа вариантов N₈ и N₉, то есть искомое число вариантов равно произведению

$M=N_8 умножить на N_9=81 умножить на 149=12 069.$

Заметим, что нами получена рекуррентная формула $N_k плюс 3=N_k плюс N_k плюс 1 плюс N_k плюс 2 :$ которая справедлива для любого натурального k.

Ответ: $M=12 069.$

Приведем другое решение.

Заметим, на каждом из двух пролетов лестницы десятиклассник Вася спускается отдельно от другого пролета, поэтому можно найти число способов спуститься для каждого пролета в отдельности и перемножить полученные два числа вариантов.

Решим задачу для пролета, состоящего из 8 ступенек. Будем нумеровать ступеньки цифрами от 0 до 8, где цифра 0 означает самую верхнюю ступеньку, цифра 8 самую нижнюю ступеньку, а один шаг будем обозначать в виде a – b, где a и b  — номера ступенек, на которых находился Вася за время этого шага. Также будем писать число ступенек, которые преодолел Вася за время шага.

Вася может перепрыгнуть через две ступеньки на третью ступеньку не более двух раз. Он может перепрыгнуть через две ступеньки два раза несколькими способами.

Если оставшиеся две ступеньки он преодолевает одним шагом, то имеется всего три варианта:

Шаги	0−3−6−8	0−3−5−8	0−2−5−8
Число ступенек	3, 3, 2	3, 2, 3	2, 3, 3

Если же оставшиеся две ступеньки он преодолевает двумя шагами, то имеется всего шесть вариантов:

Шаги	0−3−6−7−8	0−3−4−5−8	0−1−2−5−8
Число ступенек	3, 3, 1, 1	3, 1, 1, 3	1, 1, 3, 3,
Шаги	0−3−4−7−8	0−1−4−5−8	0−1−4−7−8
Число ступенек	3, 1, 3, 1	1, 3, 1, 3	1, 3, 1, 3

Таким образом, получаем $n_2=9$ вариантов.

Вася перепрыгнуть через две ступеньки один раз несколькими способами, для каждого варианта запишем для краткости только число ступенек.

Число	3, 1, 1, 1, 1, 1	3, 1, 1, 1, 2	3, 1, 1, 2, 1	3, 1, 2, 1, 1	3, 2, 1, 1, 1
ступенек	3, 1, 2, 2	3, 2, 1, 2	3, 2, 2, 1
	1, 3, 1, 1, 1, 1	1, 3, 1, 1, 2	1, 3, 1, 2, 1	1, 3, 2, 1, 1	1, 3, 2, 2
	1, 1, 3, 1, 1, 1	1, 1, 3, 1, 2	1, 1, 3, 2, 1
	2, 3, 1, 1, 1	2, 3, 1, 2	2, 3, 2, 1

Полученное число вариантов нужно умножить н 2 из-за симметрии относительно середины лестничного пролета. Таким образом, получаем $n_1=2 умножить на 19=38$ вариантов. Наконец, Вася может ни одного раза не перепрыгнуть через две ступеньки. В этом случае он может несколько раз перепрыгнуть через одну ступеньку.

Если Вася перепрыгнул через одну ступеньку четыре раза, то такой вариант один: 0−2−4−6−8.

Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить две единицы рядом с тремя двойками. При этом есть четыре вариант а расставить единицы рядом.

Число ступенек

2, 2, 2, 1, 1

2, 2, 1, 1, 2

2, 1, 1, 2, 2

1, 1, 2, 2, 2

A также есть $C_4 в квадрате =6$   — шесть вариантов расставить единички не рядом.

Число ступенек	2, 2, 1, 2, 1	2, 1, 2, 2, 1	1, 2, 2, 2, 1	2, 1, 2, 1, 2
	1, 2, 2, 1, 2	1, 2, 1, 2, 2

Если Вася перепрыгнул через одну ступеньку два раза, то таких вариантов несколько. Это число равно числу вариантов расставить две двойки рядом с четырьмя единицами.

При этом есть пять вариантов расставить двойки рядом.

Число ступенек	2, 2, 1, 1, 1, 1	1, 2, 2, 1, 1, 1	1, 1, 2, 2, 1, 1	1, 1, 1, 2, 2, 1
	1, 1, 1, 1, 2, 2

А также есть $C_5 в квадрате =10$   — десять вариантов расставить двойки не рядом.

Число ступенек	2, 1, 2, 1, 1, 1	2, 1, 1, 2, 1, 1	2, 1, 1, 1, 2, 1	2, 1, 1, 1, 1, 2
	1, 2, 1, 2, 1, 1	1, 2, 1, 1, 2, 1	1, 2, 1, 1, 1, 2	1, 1, 2, 1, 2, 1
	1, 1, 2, 1, 1, 2	1, 1, 1, 2, 1, 2

Если Вася перепрыгнул через одну ступеньку один раз, то таких вариантов несколько. Это число равно числу вариантов расставить одну двойку рядом с шестью единицами, то есть имеется семь вариантов.

Число ступенек	2, 1, 1, 1, 1, 1, 1	1, 2, 1, 1, 1, 1, 1	1, 1, 2, 1, 1, 1, 1	1, 1, 1, 2, 1, 1, 1
	1, 1, 1, 1, 2, 1, 1	1, 1, 1, 1, 1, 2, 1	1, 1, 1, 1, 1, 1, 2

Наконец, если Вася вообще не перепрыгивал через ступеньки, тогда имеется только один вариант: 0−1−2−3−4−5−6−7−8 с числом ступенек 1, 1, 1, 1, 1, 1, 1, 1.

Поэтому если Вася не перепрыгивал через две ступеньки ни одного раза, то число вариантов равно

$n_0=1 плюс 4 плюс 6 плюс 5 плюс 10 плюс 7 плюс 1=34.$

Таким образом, искомое число вариантов для пролета из 8 ступенек равно

$N_8=n_2 плюс n_1 плюс n_0=9 плюс 38 плюс 34=81.$

Теперь решим задачу для пролета, состоящего из 9 ступенек. Будем нумеровать ступеньки цифрами от 0 до 9, где цифра 0 означает самую верхнюю ступеньку, цифра 9  — самую нижнюю ступеньку.

Вася может перепрыгнуть через две ступеньки на третью ступеньку не более трех paз.

Если Вася перепрыгнул через две ступеньки на третью ступеньку три раза, то имеется только один вариант: 0−3−6−9. Поэтому получаем $m_3=1$ вариант.

Вася может перепрыгнуть через две ступеньки дв раза несколькими способами. Оставшиеся три ступеньки он может преодолеть по разному.

Если он один раз перепрыгивает через одну ступеньку, то имеется двенадцать вариантов:

Шаги	0−3−6−8−9	0−3−5−8−9	0−2−5−8−9
Число ступенек	3, 3, 2, 1	3, 2, 3, 1	2, 3, 3, 1
Шаги	0−3−6−7−9	0−3−5−6−9	0−2−5−6−9
Число ступенек	3, 3, 1, 2	3, 2, 1, 3	2, 3, 1, 3
Шаги	0−3−4−7−9	0−3−4−6−9	0−2−3−6−9
Число ступенек	3, 1, 3, 2	3, 1, 2, 3	2, 1, 3, 3
Шаги	0−1−4−7−9	0−1−4−6−9	0−1−3−6−9
Число ступенек	1, 3, 3, 2	1, 3, 2, 3	1, 2, 3, 3

Если же оставшиеся три ступеньки он преодолевает тремя шагами, то имеется всего десять вариантов:

Шаги	0−3−6−7−8−9	0−3−4−5−6−9	0−1−2−3−6−9
Число ступенек	3, 3, 1, 1, 1	3, 1, 1, 1, 3	1, 1, 1, 3, 3
Шаги	0−3−4−7−8−9	0−1−4−7−8−9	0−3−4−5−8−9
Число ступенек	3, 1, 3, 1, 1	1, 3, 3, 1, 1	3, 1, 1, 3, 1
Шаги	0−1−4−5−6−9	0−1−2−5−8−9	0−1−2−5−6−9
Число ступенек	1, 3, 1, 1, 3	1, 1, 3, 3, 1	1, 1, 3, 1, 3
Шаги	0−1−4−5−8−9
Число ступенек	1, 3, 1, 3, 1

Таким образом, получаем $m_2=12 плюс 10=22$ варианта.

Вася может перепрыгнуть через две ступеньки один раз несколькими способами. Оставшиеся шесть ступенек он может преодолеть по разному.

Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить три двойки рядом с одной тройкой, то есть имеется четыре варианта. Для каждого варианта запишем для краткости только число ступенек.

Число ступенек

2, 2, 2, 3

2, 2, 3, 2

2, 3, 2, 2

3, 2, 2, 2

Если Вася перепрыгнул через одну ступеньку два раза, то таких вариантов несколько. Это число равно числу вариантов расставить две двойки и две единицы рядом с одной тройкой, то есть имеется тридцать таких вариантов.

Число	2, 2, 3, 1, 1	2, 2, 1, 1, 3	2, 1, 1, 2, 3	1, 1, 2, 2, 3
ступенек	2, 2, 1, 3, 1	2, 1, 2, 3, 1	1, 2, 2, 3, 1	2, 1, 2, 1, 3	1, 2, 2, 1, 3
	1, 2, 1, 2, 3
	2, 3, 2, 1, 1	2, 3, 1, 1, 2	2, 1, 1, 3, 2	1, 1, 2, 3, 2
	2, 3, 1, 2, 1	2, 1, 3, 2, 1	1, 2, 3, 2, 1	2, 1, 3, 1, 2	1, 2, 3, 1, 2
	1, 2, 1, 3, 2
	3, 2, 2, 1, 1	3, 2, 1, 1, 2	3, 1, 1, 2, 2	1, 1, 3, 2, 2
	3, 2, 1, 2, 1	3, 1, 2, 2, 1	1, 3, 2, 2, 1	3, 1, 2, 1, 2	1, 3, 2, 1, 2
	1, 3, 1, 2, 2

Если Вася перепрыгнул через одну ступеньку один раз, то таких вариантов несколько. Это число равно числу вариантов расставить четыре единицы рядом с одной двойкой и одной тройкой, то есть имеется тридцать таких вариантов.

Число	2, 3, 1, 1, 1, 1	2, 1, 1, 1, 1, 3	1, 1, 1, 1, 2, 3
ступенек	2, 1, 3, 1, 1, 1	1, 2, 3, 1, 1, 1	2, 1, 1, 1, 3, 1	1, 2, 1, 1, 1, 3	1, 1, 1, 2, 3, 1
	1, 1, 1, 2, 1, 3
	2, 1, 1, 3, 1, 1	1, 1, 2, 3, 1, 1	1, 1, 2, 1, 1, 3
	1, 2, 1, 3, 1, 1	1, 2, 1, 1, 3, 1	1, 1, 2, 1, 3, 1
	3, 1, 2, 1, 1, 1	1, 3, 2, 1, 1, 1	3, 1, 1, 1, 2, 1	1, 3, 1, 1, 1, 2	1, 1, 1, 3, 2, 1
	1, 1, 1, 3, 1, 2
	3, 1, 1, 2, 1, 1	1, 1, 3, 2, 1, 1	1, 1, 3, 1, 1, 2
	1, 3, 1, 2, 1, 1	1, 3, 1, 1, 2, 1	1, 1, 3, 1, 2, 1

Если же Вася ни разу не перепрыгнул через одну ступеньку, то таких вариантов несколько. Это число равно числу вариантов расставить шесть единиц рядом с одной тройкой, то есть имеется семь таких вариантов.

Число ступенек	3, 1, 1, 1, 1, 1, 1	1, 3, 1, 1, 1, 1, 1	1, 1, 3, 1, 1, 1, 1	1, 1, 1, 3, 1, 1, 1
	1, 1, 1, 1, 3, 1, 1	1, 1, 1, 1, 1, 3, 1	1, 1, 1, 1, 1, 1, 3

Таким образом, получаем $m_1=4 плюс 30 плюс 30 плюс 7=71$ вариант.

Наконец, Вася может ни одного раза не перепрыгнуть через две ступеньки. В этом случае он может несколько раз перепрыгнуть через одну ступеньку.

Если Вася перепрыгнул через одну ступеньку четыре раза, то таких вариантов несколько. Это число равно числу вариантов расставить одну единицу рядом с четырьмя Двойками, то есть имеется пять вариантов.

Число ступенек	2, 2, 2, 2, 1	2, 2, 2, 1, 2	2, 2, 1, 2, 2	2, 1, 2, 2, 2
	1, 2, 2, 2, 2

Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить три единицы рядом с тремя двойками.

При этом есть четыре варианта расставить единицы рядом.

Число ступенек

2, 2, 2, 1, 1, 1

2, 2, 1, 1, 1, 2

2, 1, 1, 1, 2, 2

1, 1, 1, 2, 2, 2

И есть $4 умножить на 3=12$   — двенадцать вариантов расставить только две единицы рядом.

Число ступенек	2, 2, 1, 2, 1, 1	2, 1, 2, 2, 1, 1	1, 2, 2, 2, 1, 1
	2, 2, 1, 1, 2, 1	2, 1, 2, 1, 1, 2	1, 2, 2, 1, 1, 2
	2, 1, 1, 2, 2, 1	2, 1, 1, 2, 1, 2	1, 2, 1, 1, 2, 2
	1, 1, 2, 2, 2, 1	1, 1, 2, 2, 1, 2	1, 1, 2, 1, 2, 2

А также есть $C_4 в кубе =4$   — четыре варианта расставить единички не рядом.

Число ступенек

2, 1, 2, 1, 2, 1

1, 2, 2, 1, 2, 1

1, 2, 1, 2, 2, 1

1, 2, 1, 2, 1, 2

Если Вася перепрыгнул через одну ступеньку два раза, то таких вариантов несколько. Это число равно числу вариантов расставить две двойки рядом с пятью единицами.

При этом есть шесть вариантов расставить двойки рядом.

Число ступенек	2, 2, 1, 1, 1, 1, 1	1, 2, 2, 1, 1, 1, 1	1, 1, 2, 2, 1, 1, 1	1, 1, 1, 2, 2, 1, 1
	1, 1, 1, 1, 2, 2, 1	1, 1, 1, 1, 1, 2, 2

А также есть $C_6 в квадрате =15$   — пятнадцать вариантов расставить двойки не рядом.

Число ступенек	2, 1, 2, 1, 1, 1, 1	2, 1, 1, 2, 1, 1, 1	2, 1, 1, 1, 2, 1, 1	2, 1, 1, 1, 1, 2, 1
	2, 1, 1, 1, 1, 1, 2	1, 2, 1, 2, 1, 1, 1	1, 2, 1, 1, 2, 1, 1	1, 2, 1, 1, 1, 2, 1
	1, 2, 1, 1, 1, 1, 2	1, 1, 2, 1, 2, 1, 1	1, 1, 2, 1, 1, 2, 1	1, 1, 2, 1, 1, 1, 2
	1, 1, 1, 2, 1, 2, 1	1, 1, 1, 2, 1, 1, 2	1, 1, 1, 1, 2, 1, 2

Если Вася перепрыгнул через одну ступеньку один раз, то таких вариантов несколько. Это число равно числу вариантов расставить одну двойку рядом с семью единицами, то есть имеется восемь вариантов.

число ступенек	2, 1, 1, 1, 1, 1, 1, 1	1, 2, 1, 1, 1, 1, 1, 1	1, 1, 2, 1, 1, 1, 1, 1	1, 1, 1, 2, 1, 1, 1, 1
	1, 1, 1, 1, 2, 1, 1, 1	1, 1, 1, 1, 1, 2, 1, 1	1, 1, 1, 1, 1, 1, 2, 1	1, 1, 1, 1, 1, 1, 1, 2

Наконец, если Вася вообще не перепрыгивал через ступеньки, тогда имеется только один вариант: 0−1−2−3−4−5−6−7−8−9 с числом ступенек 1, 1, 1, 1, 1, 1, 1, 1, 1.

Поэтому если Вася не перепрыгивал через две ступеньки ни одного раза, то число вариантов равно

$n_0=5 плюс 4 плюс 12 плюс 4 плюс 6 плюс 15 плюс 8 плюс 1=55.$

Таким образом, искомое число вариантов для пролета из 9 ступенек равно

$N_9=m_3 плюс m_2 плюс m_1 плюс m_0=1 плюс 22 плюс 71 плюс 55=149.$

Наконец, искомое число вариантов равно произведению

$M=N_8 умножить на N_9=81 умножить на 149=12 069.$

Решение · Помощь

Всего: 5 1–5